package org.apache.commons.graph.algorithms.shortestpath

import org.apache.commons.graph.Graph
import org.apache.commons.graph.Mapper
import org.apache.commons.graph.algorithms.shortestpath.exception.NegativeWeightedCycleException
import org.apache.commons.graph.algorithms.shortestpath.exception.PathNotFoundException
import org.apache.commons.graph.algorithms.shortestpath.internal.ShortestDistances
import org.apache.commons.graph.weight.OrderedMonoid

/*
* Licensed to the Apache Software Foundation (ASF) under one
* or more contributor license agreements.  See the NOTICE file
* distributed with this work for additional information
* regarding copyright ownership.  The ASF licenses this file
* to you under the Apache License, Version 2.0 (the
* "License"); you may not use this file except in compliance
* with the License.  You may obtain a copy of the License at
*
*   http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing,
* software distributed under the License is distributed on an
* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
* KIND, either express or implied.  See the License for the
* specific language governing permissions and limitations
* under the License.
*/

/**
 *
 *
 * @param <V> the Graph vertices type.
 * @param <WE> the Graph weighted edges type
 * @param <W> the weight type
</W></WE></V> */
interface TargetSourceSelector<V, WE, W> {
    /**
     * Calculates the shortest path using the BellmannFord's algorithm.
     *
     * @param <WO> the type of weight operations
     * @param weightOperations the weight operations needed for the algorithm
     * @return a data structure which contains all vertex pairs shortest path.
    </WO> */
    fun <WO : OrderedMonoid<W>> applyingBelmannFord(weightOperations: WO): AllVertexPairsShortestPath<V, WE, W>

    /**
     * Specifies the shortest path source.
     *
     * @param target
     */
    fun <T : V> to(target: T): ShortestPathAlgorithmSelector<V, WE, W>
}



/*
* Licensed to the Apache Software Foundation (ASF) under one
* or more contributor license agreements.  See the NOTICE file
* distributed with this work for additional information
* regarding copyright ownership.  The ASF licenses this file
* to you under the Apache License, Version 2.0 (the
* "License"); you may not use this file except in compliance
* with the License.  You may obtain a copy of the License at
*
*   http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing,
* software distributed under the License is distributed on an
* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
* KIND, either express or implied.  See the License for the
* specific language governing permissions and limitations
* under the License.
*/

internal class DefaultTargetSourceSelector<V, WE, W>(
    private val graph: Graph<V, WE>,
    private val weightedEdges: Mapper<WE, W>,
    private val source: V
) : TargetSourceSelector<V, WE, W> {

    override fun <WO : OrderedMonoid<W>> applyingBelmannFord(weightOperations: WO): AllVertexPairsShortestPath<V, WE, W> {
//        var weightOperations = weightOperations
//        weightOperations = Assertions.checkNotNull(
//            weightOperations,
//            "Belmann-Ford algorithm can not be applied using null weight operations"
//        )

        val shortestDistances = ShortestDistances<V, W>(weightOperations)
        shortestDistances.setWeight(source, weightOperations.identity())

        val predecessors = org.apache.commons.graph.algorithms.shortestpath.PredecessorsList(
            graph,
            weightOperations,
            weightedEdges
        )

        for (i in 0..<graph.order) {
            for (edge in graph.edges) {
                val vertexPair = graph.getVertices(edge)
                val u = vertexPair!!.head
                val v = vertexPair.tail

                if (shortestDistances.alreadyVisited(u)) {
                    val shortDist = weightOperations.append(shortestDistances.getWeight(u)!!, weightedEdges.map(edge))

                    if (!shortestDistances.alreadyVisited(v)
                        || weightOperations.compare(shortDist, shortestDistances.getWeight(v)) < 0
                    ) {
                        // assign new shortest distance and mark unsettled
                        shortestDistances.setWeight(v, shortDist)

                        // assign predecessor in shortest path
                        predecessors.addPredecessor(v, u)
                    }
                }
            }
        }

        for (edge in graph.edges) {
            val vertexPair = graph.getVertices(edge)
            val u = vertexPair!!.head
            val v = vertexPair.tail

            if (shortestDistances.alreadyVisited(u)) {
                val shortDist = weightOperations.append(shortestDistances.getWeight(u)!!, weightedEdges.map(edge))

                if (!shortestDistances.alreadyVisited(v)
                    || weightOperations.compare(shortDist, shortestDistances.getWeight(v)) < 0
                ) {
                    // TODO it would be nice printing the cycle
                    throw NegativeWeightedCycleException(
                        "Graph contains a negative-weight cycle in vertex %s",
                        v, graph
                    )
                }
            }
        }

        val allVertexPairsShortestPath = AllVertexPairsShortestPath<V, WE, W>(weightOperations)

        for (target in graph.vertices) {
            if (source != target) {
                try {
                    val weightedPath = predecessors.buildPath(source, target)
                    allVertexPairsShortestPath.addShortestPath(source, target, weightedPath)
                } catch (e: PathNotFoundException) {
                    continue
                }
            }
        }

        return allVertexPairsShortestPath
    }

    /**
     * {@inheritDoc}
     */
    override fun <T : V> to(target: T): ShortestPathAlgorithmSelector<V, WE, W> {
        //var target = target
        //target = Assertions.checkNotNull(target, "Shortest path can not be calculated to a null target")
        return DefaultShortestPathAlgorithmSelector(graph, weightedEdges, source, target)
    }

}